// 1、无头单向非循环链表实现
 public class SingleLinkedList {
    static class Node {
        public int val;
        public Node next;

        public Node(int val) {
            this.val = val;
        }
    }
    public Node head;
     //头插法
     public void addFirst(int data) {
         Node node = new Node(data);
         node.next = head;
         head = node;
     };
     //尾插法
     public void addLast(int data) {
         Node node = new Node(data);
         if(head == null) {
             head = node;
         }
         Node tmp = head;
         while(tmp != null) {
             if(tmp.next == null) {
                 tmp.next = node;
                 return;
             }
             tmp = tmp.next;
         }
     };
     //任意位置插入,第一个数据节点为0号下标
     public boolean addIndex(int index,int data) {
         Node node = new Node(data);
         //判断index是否合法
         if(index < 0 || index > size()) {
             return false;
         }
         //头插法
         if(index == 0) {
             addFirst(data);
             return true;
         }
         //尾插法
         if(index == size()) {
             addLast(data);
             return true;
         }
         //插入中间
         //找到插入位置的前一个节点
         Node tmp = head;
         int i = 1;
         while(i < index) {
             tmp = tmp.next;
             i++;
         }
         node.next = tmp.next;
         tmp.next = node;
         return true;
     };
     //查找是否包含关键字key是否在单链表当中
     public boolean contains(int key) {
         Node tmp = head;
         while(tmp != null) {
             if(tmp.val == key) {
                 return true;
             }
             tmp = tmp.next;
         }
         return false;
     };
     //删除第一次出现关键字为key的节点
     public void remove(int key) {
         if(head == null) {
             return;
         }
         //判断第一个节点是不是需要删除的节点
         if(head.val == key) {
             head = null;
             return;
         }
         Node tmp = head;
         while(tmp.next != null) {
             if(tmp.next.val == key) {
                 tmp.next = tmp.next.next;
                 return;
             }
             tmp = tmp.next;
         }
     };
     //删除所有值为key的节点
     public void removeAllKey(int key) {
         if(head == null) {
             return;
         }
         Node node = head;
         Node right = head.next;
         while(right != null) {
             if(right.val == key) {
                 node.next = right.next;
             }else {
                 node = node.next;
             }
             right = right.next;
         }
         //判断第一个节点是不是要删除的元素
         if(head.val == key) {
             head = head.next;
         }
     };
     //得到单链表的长度
     public int size() {
         int count = 0;
         Node tmp =  head;
         while(tmp != null) {
             count++;
             tmp = tmp.next;
         }
         return count;
     };
     //打印链表
     public void display() {
         Node tmp = head;
         while(tmp != null) {
             System.out.print(tmp.val + " ");
             tmp = tmp.next;
         }
         System.out.println();
     };
     //清除链表
     public void clear() {
         //这里将所有节点都回收
         Node node = head;
         Node nodeNext = null;
         while(node != null) {
             nodeNext = node.next;
             node.next = null;
             node = nodeNext;
         }
         head = null;
     };

 }